#判断是否为回文串
def isPalindrome(s, start, end):
    a = start
    b = end
    while a < b:
        if s[a] != s[b]:
            return False
        a += 1
        b -= 1
    return True

def partition(s):
    result = []
    def backtrack(start, sublist):
        if start == len(s):
            result.append(sublist)
            return
        for end in range(start, len(s)):
            if isPalindrome(s, start, end):
                backtrack(end + 1, sublist + [s[start:end+1]])
    backtrack(0, [])
    return result

s = "google"
print(partition(s))
